%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Probability and Its Applications
%% http://code.google.com/p/probability-book/
%%
%% Copyright (C) 2010 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Balls, Bins, and Random Graphs}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The birthday paradox}

Given a group of $30$ people, the \emph{birthday paradox} asks for the
probability that two people from that group share the same
birthday. We can model this problem as follows. Assume that the
birthday of each person is a day chosen independently and uniformly at
random from a $365$-day year. Such assumptions help in simplifying the
analysis to gain some initial understanding of the full problem
itself. We could incorporate further information into our analysis by
considering, say, leap years and twins.

One way to directly compute the probability in question is to consider
the configurations where two people share different birthdays. From
among the $365$ days we choose $30$ days, giving a total of
$\binom{365}{30}$ possibilities. The $30$ days can be assigned to the
people in a total of $30!$ possible ways. Hence there are
$\binom{365}{30} \cdot 30!$ possible configurations in which any two
people share different birthdays. Since there are $365^{30}$ ways the
birthdays could occur, the probability that $30$ people share
different birthday is
\[
\frac{\binom{365}{30} \cdot 30!} {365^{30}}.
\]

An alternative method to compute this probability is to consider each
person at a time. The first person out of the group of $30$ has a
birthday. The probability that the second person has a birthday
different from the first is $1 - 1/365$. Given that the first two
people share different birthdays, the probability that the third
person has a birthday distinct from the first two is $1 - 2/365$.
Using the same argument, given that the first $k - 1$ people have
birthdays different from one another, the probability that the $k$-th
person has a birthday distinct from the first $k - 1$ people is given
by $1 - (k - 1)/365$. We conclude that among $30$ people, the
probability that they all have birthdays distinct from one another is
\[
\prod_{i=1}^{29} \left(1 - \frac{i}{365}\right).
\]
Thus among $30$ people, the probability that two of them share the
same birthday is
\[
1 - \prod_{i=1}^{29} \left(1 - \frac{i}{365}\right).
\]

We can generalize to the case of $m$ people and $n$ possible
birthdays. In a group of $m$ people, the probability that they all
have birthdays distinct from each other is
%%
\begin{equation}
\label{eq:balls-bins:birthday_paradox:m_people_n_birthdays}
\prod_{i=1}^{m-1} \left(1 - \frac{i}{n}\right).
\end{equation}
%%
To approximate the
probability~\eqref{eq:balls-bins:birthday_paradox:m_people_n_birthdays},
recall that $1 - k/n \approx e^{-k/n}$ when $k < n$. When $m < n$, the
product~\eqref{eq:balls-bins:birthday_paradox:m_people_n_birthdays}
can be approximated as follows:
%%
\begin{align*}
\prod_{i=1}^{m-1} \left(1 - \frac{i}{n}\right)
&\approx
\prod_{i=1}^{m-1} e^{-i/n} \\[4pt]
&=
\exp\left(- \sum_{i=1}^{m-1} \frac{i}{n}\right) \\[4pt]
&=
e^{-m(m-1) / 2n} \\
&\approx
e^{-m^2 / 2n}.
\end{align*}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Balls and bins}

The birthday paradox is an instance of a general framework often
formulated in terms of balls and bins. We throw $m$ balls into $n$
bins, where the location at which a ball lands is chosen independently
and uniformly at random from among the $n$ possibilities. What is the
distribution of the balls in the bins?

\begin{lemma}
Let $m$ balls be thrown independently and uniformly at random into $n$
bins. The maximum load of a bin is the maximum number of balls that
the bin can hold. Then the probability that the maximum load is
$> 3 \cdot (\ln n) / (\ln \ln n)$ is at most $1/n$ for sufficiently
large $n$.
\end{lemma}

\begin{proof}
There are $\binom{n}{M}$ distinct combinations of $M$ balls. For any
combination of $M$ balls, the probability that all land in bin $1$ is
$(1/n)^M$. Thus the probability that bin $1$ has at least $M$ balls is
at most
\[
\binom{n}{M} \left(\frac{1}{n}\right)^M.
\]
Note that
\[
\binom{n}{M} \left(\frac{1}{n}\right)^M
\leq
\frac{1}{M!}
\leq
\left(\frac{e}{M}\right)^M
\]
where the second inequality is obtained as follows. Since
\[
\frac{k^k}{k!}
<
\sum_{i=0}^\infty \frac{k^i}{i!}
=
e^k
\]
then
\[
k!
>
\left(\frac{k}{e}\right)^k.
\]
Applying a union bound, when $M \geq 3 \cdot (\ln n) / (\ln \ln n)$ the
probability that any bin has at least $M$ balls is bounded above by
%%
\begin{align*}
n \cdot \left(\frac{e}{M}\right)^M
&\leq
n \cdot \left(\frac{e \cdot \ln{\ln n}} {3 \cdot \ln{n}}\right)^{3 \cdot (\ln n) / (\ln \ln n)} \\[4pt]
&\leq
n \cdot \left(\frac{\ln{\ln n}} {\ln n}\right)^{3 \cdot (\ln n) / (\ln \ln n)} \\[4pt]
&=
\exp\left\{-2 \cdot \ln{n} + \frac{3 \cdot (\ln{n}) \cdot (\ln{\ln \ln n})} {\ln{\ln n}}\right\} \\[4pt]
&\leq
\frac{1}{n}
\end{align*}
%%
for sufficiently large $n$.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The Poisson distribution}

Consider again $m$ balls and $n$ bins. What is the probability that a
given bin is empty? What is the expected number of empty bins? If the
first bin is empty, then it is missed by the $m$ balls. Each ball
lands in the first bin with probability $1/n$. The probability that
the first bin is empty is
\[
\left(1 - \frac{1}{n}\right)^m
\approx
e^{-m/n}
\]
which is also the probability that any bin is empty. Define the random
variable $X_i$ by
\[
X_i
=
\begin{cases}
1, & \text{if the $i$-th bin is empty}, \\
0, & \text{otherwise}
\end{cases}
\]
and we have the expectation $\E[X_i] = \left(1 - \frac{1}{n}\right)^m$.
Let $X$ be a random variable representing the number of empty bins. By
the linearity of expectations we have
\[
\E[X]
=
\E\left[\sum_{i=1}^n X_i\right]
=
\sum_{i=1}^n \E[X_i]
=
n \cdot \left(1 - \frac{1}{n}\right)^m
\approx
n \cdot e^{-m/n}
\]
and the expected fraction of empty bins is $\approx e^{-m/n}$.

We now generalize the preceding argument to determine the expected
fraction of bins with $r$ balls for any constant $r > 0$. Given a
constant $r > 0$, the probability that a given bin has $r$ balls is
\[
\binom{m}{r} \left(\frac{1}{n}\right)^r \left(1 - \frac{1}{n}\right)^{m-r}
=
\frac{1}{r!} \cdot
\frac{m(m-1) \cdots (m - r + 1)}{n^r} \cdot
\left(1 - \frac{1}{n}\right)^{m-r}.
\]
If $r < m,n$ then
\[
\frac{m(m-1) \cdots (m - r + 1)}{n^r}
\approx
\left(\frac{m}{n}\right)^r
\]
and
\[
\left(1 - \frac{1}{n}\right)^{m-r}
\approx
e^{-m/n}.
\]
Denote by $P_r$ the probability that a given bin has $r$ balls. Then
we have the approximation
\[
P_r
\approx
\frac{e^{-m/n} (m/n)^r} {r!}
\]
so that the expected number of bins with $r$ balls is $n \cdot P_r$.

For $i = 0, 1, 2, \dots$, a \emph{discrete Poisson random variable}
$X$ with parameter $\mu$ is defined as the probability distribution
\[
\Pr(X = i)
=
\frac{e^{-\mu} \mu^i}{i!}.
\]
We now verify that this definition results in a proper distribution,
i.e. the probabilities sum to $1$. Recall that the Taylor expansion of
$e^x$ is
\[
e^x
=
\sum_{i=0}^\infty \frac{x^i}{i!}.
\]
Use this Taylor expansion to obtain
%%
\begin{align*}
\sum_{i=0}^\infty \Pr(X = i)
&=
\sum_{i=0}^\infty \frac{e^{-\mu} \mu^i}{i!} \\[4pt]
&=
e^{-\mu} \sum_{i=0}^\infty \frac{\mu^i}{i!} \\[4pt]
&=
e^{-\mu} \cdot e^\mu.
\end{align*}
%%
The expectation of the discrete Poisson random variable $X$ is
therefore
%%
\begin{align*}
\E[X]
&=
\sum_{i=0}^\infty i \cdot \Pr(X = i) \\[4pt]
&=
\sum_{i=1}^\infty i \cdot \frac{e^{-\mu} \mu^i}{i!} \\[4pt]
&=
\mu \sum_{i=1}^\infty \frac{e^{-\mu} \mu^{i-1}}{(i-1)!} \\[4pt]
&=
\mu \sum_{i=0}^\infty \frac{e^{-\mu} \mu^i}{i!} \\[4pt]
&=
\mu.
\end{align*}

\begin{lemma}
\label{lem:balls-bins:sum_Poisson_random_variables}
Let $X_1, \dots, X_n$ be a collection of independent Poisson random
variables. Then $X = \sum_i X_i$ is a Poisson random variable.
\end{lemma}

\begin{proof}
We use an inductive argument on the number of independent Poisson
random variables. For the base case, let $X$ and $Y$ be independent
Poisson random variables with means $\mu_1$ and $\mu_2$,
respectively. Use the binomial theorem to obtain
%%
\begin{align*}
\Pr(X + Y = i)
&=
\sum_{k=0}^i \Pr\big((X = k) \cap (Y = i-k)\big) \\[4pt]
&=
\sum_{k=0}^i \frac{e^{-\mu_1} \mu_1^k}{k!} \cdot
\frac{e^{-\mu_2} \mu_2^{i-k}}{(i-k)!} \\[4pt]
&=
\frac{e^{-(\mu_1 + \mu_2)}}{i!} \cdot
\sum_{k=0}^i \frac{i!}{k! (i-k)!} \cdot \mu_1^k \mu_2^{i-k} \\[4pt]
&=
\frac{e^{-(\mu_1 + \mu_2)}}{i!} \cdot
\sum_{k=0}^i \binom{i}{k} \mu_1^k \mu_2^{i-k} \\[4pt]
&=
\frac{e^{-(\mu_1 + \mu_2)} (\mu_1 + \mu_2)^i}{i!}.
\end{align*}
%%
The inductive case is similarly handled.
\end{proof}

\begin{lemma}
\label{lem:balls-bins:moment_genfunction_discrete_Poisson_random_var}
The moment generating function of a discrete Poisson random variable
$X$ with parameter $\mu$ is
\[
M_X(t)
=
e^{\mu(e^t - 1)}.
\]
\end{lemma}

\begin{proof}
For any $t$ we have
%%
\begin{align*}
M_X(t)
&=
\E\big[e^{tX}\big] \\[4pt]
&=
\sum_{i=0}^\infty e^{ti} \cdot \frac{e^{-\mu} \mu^i}{i!} \\[4pt]
&=
e^{\mu(e^t - 1)} \cdot \sum_{i=0}^\infty \frac{e^{-\mu e^t} (\mu e^t)^i}{i!} \\[4pt]
&=
e^{\mu(e^t - 1)}
\end{align*}
%%
as required.
\end{proof}

If $X$ and $Y$ are independent Poisson random variables with means
$\mu_1$ and $\mu_2$, respectively, apply
Theorem~\ref{thm:chernoff:sum_product_of_moments} and
Lemma~\ref{lem:balls-bins:moment_genfunction_discrete_Poisson_random_var}
to obtain
%%
\begin{align*}
M_{X+Y}(t)
&=
M_X(t) \cdot M_Y(t) \\
&=
e^{\mu_1(e^t - 1)} \cdot e^{\mu_2(e^t - 1)} \\
&=
\exp\left\{(\mu_1 + \mu_2) (e^t - 1)\right\}
\end{align*}
%%
which is the moment generating function of a discrete Poisson random
variable with mean $\mu_1 + \mu_2$. From
Theorem~\ref{thm:chernoff:two_random_var_same_distribution}, the
moment generating function uniquely defines the
distribution. Therefore $X + Y$ is a discrete Poisson random variable
with mean $\mu_1 + \mu_2$.

\begin{theorem}
Denote by $X$ a Poisson random variable with parameter $\mu$. Then we
have the following Chernoff bounds.
%%
\begin{enumerate}
\item If $x > \mu$, then
  \[
  \Pr(X \geq x)
  \leq
  \frac{e^{-\mu} (e\mu)^x}{x^x}.
  \]

\item If $x < \mu$, then
  \[
  \Pr(X \leq x)
  \leq
  \frac{e^{-\mu} (e\mu)^x}{x^x}.
  \]
\end{enumerate}
\end{theorem}

\begin{proof}
Given any $t > 0$ and $x > \mu$, use Markov's inequality and the
moment generating function of the Poisson
distribution~(Lemma~\ref{lem:balls-bins:moment_genfunction_discrete_Poisson_random_var})
to get
%%
\begin{align*}
\Pr(X \geq x)
&=
\Pr\left(e^{tX} \geq e^{tx}\right) \\[4pt]
&\leq
\frac{\E\big[e^{tX}\big]}{e^{tx}} \\[4pt]
&=
\frac{e^{\mu(e^t - 1)}}{e^{tx}} \\[4pt]
&=
\exp\left\{\mu(e^t - 1) - tx\right\}.
\end{align*}
%%
Set $t = \ln (x/\mu) > 0$ to obtain
\[
\Pr(X \geq x)
\leq
\exp\big\{x - \mu - x \cdot \ln(x/\mu)\big\}
=
\frac{e^{-\mu} (e\mu)^x}{x^x}.
\]

Given any $t < 0$ and $x < \mu$, the second Chernoff bound can be
derived using an argument similar to that used for deriving the first
Chernoff bound. That is, apply Markov's inequality and
Lemma~\ref{lem:balls-bins:moment_genfunction_discrete_Poisson_random_var}
to get
%%
\begin{align*}
\Pr(X \leq x)
&=
\Pr(e^{tX} \geq e^{tx}) \\[4pt]
&\leq
\frac{\E\big[e^{tX}\big]}{e^{tx}} \\[4pt]
&=
\exp\big\{\mu(e^t - 1) - tx\big\}.
\end{align*}
%%
Setting $t = \ln(x/\mu) < 0$ to obtain
%%
\begin{align*}
\Pr(X \leq x)
&\leq
\exp\big\{x - \mu - x \cdot \ln(x/\mu)\big\} \\[4pt]
&=
\frac{e^{-\mu}(e\mu)^x}{x^x}
\end{align*}
%%
as required.
\end{proof}

In a binomial distribution with parameters $n$ and $p$, as $n \to \infty$
and $p \to 0$ the binomial distribution can be approximated using the
Poisson distribution. More precisely, we have the following result
which says that the Poisson distribution is the limit distribution of
the binomial distribution.

\begin{theorem}
Consider a binomial distribution $X_n$ with parameters $n$ and $p$,
with $p$ being a function of $n$ and the constant
$\lim_{n \to \infty} np = \lambda$ is independent of $n$. For any
fixed $k$, we have
\[
\lim_{n \to \infty} \Pr(X_n = k)
=
\frac{e^{-\lambda} \lambda^k}{k!}.
\]
\end{theorem}

\begin{proof}
We will make use of the bound
%%
\begin{equation}
\label{eq:balls-bins:upper_bound_exp_x}
e^x (1 - x^2)
\leq
1 + x
\leq e^x
\end{equation}
%%
for $|x| < 1$, which can be derived using the Taylor series expansion
of $e^x$. Use the binomial theorem to write
%%
\begin{align*}
\Pr(X_n = k)
&=
\binom{n}{k} p^k (1 - p)^{n-k} \\[4pt]
&\leq
\frac{n^k}{k!} p^k \frac{(1 - p)^n}{(1 - p)^k} \\[4pt]
&\leq
\frac{(np)^k}{k!} \cdot \frac{e^{-pn}}{1 - pk} \\[4pt]
&=
\frac{e^{-pn} (np)^k}{k!} \cdot \frac{1}{1 - pk}
\end{align*}
%%
where we made use of the bound $(1-p)^k \geq 1 - pk$ for $k \geq 0$.
Apply~\eqref{eq:balls-bins:upper_bound_exp_x} with $x = -p$ to get
%%
\begin{align*}
\Pr(X_n = k)
&\geq
\frac{(n - k + 1)^k}{k!} \cdot p^k (1-p)^n \\[4pt]
&\geq
\frac{\big((n - k + 1) p\big)^k}{k!} \cdot e^{-pn} (1 - p^2)^n \\[4pt]
&\geq
\frac{e^{-pn} \big((n - k + 1) p\big)^k}{k!} \cdot (1 - p^2 n).
\end{align*}
%%
Hence the binomial distribution is bounded by
\[
\frac{e^{-pn} (np)^k}{k!} \cdot \frac{1}{1 - pk}
\leq
\Pr(X_n = k)
\leq
\frac{e^{-pn} \big((n - k + 1) p\big)^k}{k!} \cdot (1 - p^2 n).
\]
By hypothesis, as $n \to \infty$ we have the constant
$\lim_{n \to \infty} np = \lambda$ and so $p \to 0$. Then both
$1 / (1 - pk)$ and $1 - p^2 n$ approach $1$. The difference between
$(n - k + 1) p$ and $np$ approaches $0$. Thus in the limit we have
\[
\lim_{n \to \infty} \frac{e^{-pn} (np)^k}{k!} \cdot \frac{1}{1 - pk}
=
\frac{e^{-\lambda} \lambda^k}{k!}
\]
and
\[
\lim_{n \to \infty} \frac{e^{-pn} \big((n - k + 1) p\big)^k}{k!}
\cdot (1 - p^2 n)
=
\frac{e^{-\lambda} \lambda^k}{k!}.
\]
Therefore
\[
\lim_{n \to \infty} \Pr(X_n = k)
=
\frac{e^{-\lambda} \lambda^k}{k!}
\]
as required.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The Poisson approximation}

\begin{theorem}
\label{thm:balls_bins:throw_m_balls_into_n_bins}
Let $m$ balls be thrown independently and uniformly at random into $n$
bins. Denote by $X_i^{(m)}$ the number of balls in the $i$-th bin with
$1 \leq i \leq n$. Consider the collection $Y_1^{(m)}, \dots, Y_n^{(m)}$
of independent Poisson random variables with mean $m/n$. Then the
distribution of $\big(Y_1^{(m)}, \dots, Y_n^{(m)}\big)$ conditioned
on $k = \sum_i Y_i^{(m)}$ is equivalent to
$\big(X_1^{(m)}, \dots, X_n^{(m)}\big)$, irrespective of the value of
$m$.
\end{theorem}

\begin{proof}
In throwing $k$ balls into $n$ bins, the probability that
$\big(X_1^{(k)}, \dots, X_n^{(k)}\big) = (k_1, \dots, k_n)$ for any
$k_1, \dots, k_n$ such that $k = \sum_i k_i$ is
\[
\frac{\binom{k}{k_1; k_2; \dots; k_n}} {n^k}
=
\frac{k!} {k_1! \cdots k_n! n^k}.
\]
On the other hand, consider any $k_1, \dots, k_n$ such that
$k = \sum_i k_i$. The probability that
$\big(Y_1^{(m)}, \dots, Y_n^{m}\big) = (k_1, \dots, k_n)$ conditioned
on $k = \sum_i Y_i^{(m)}$ is given by
%%
\begin{align*}
& \Pr\left(
  \big(Y_1^{(m)}, \dots, Y_n^{(m)}\big) = (k_1, \dots, k_n)
  \;\left|\;
  k = \sum_i Y_i^{(m)}
  \right.
\right) \\[4pt]
&=
\frac{%
  \Pr\left(
  \big(Y_1^{(m)} = k_1\big) \cap \cdots \cap \big(Y_n^{(m)} = k_n\big)
  \right)
}
{\Pr\left(k = \sum_i Y_i^{(m)}\right)}.
\end{align*}
%%
As $Y_1^{(m)}, \dots, Y_n^{(m)}$ are independent Poisson random
variables with mean $m/n$, then
\[
\Pr\big(Y_i^{(m)} = k_i\big)
=
\frac{e^{-m/n} (m/n)^{k_i}}{k_i!}.
\]
By Lemma~\ref{lem:balls-bins:sum_Poisson_random_variables}, the sum
$\sum_i Y_i^{(m)}$ is a Poisson random variable with mean $m$ and
therefore
%%
\begin{align*}
\frac{%
  \Pr\left(
  \big(Y_1^{(m)} = k_1\big) \cap \cdots \cap \big(Y_n^{(m)} = k_n\big)
  \right)
} {\Pr\left(k = \sum_i Y_i^{(m)}\right)}
&=
\prod_i \frac{e^{-m/n} (m/n)^{k_i}} {k_i!}
\div \frac{e^{-m} m^k}{k!} \\[4pt]
&=
\prod_i \frac{e^{-m/n} (m/n)^{k_i}} {k_i!}
\times \frac{k!}{e^{-m} m^k} \\[4pt]
&=
\frac{k!}{k_1! \cdots k_n! n^k}
\end{align*}
%%
as required.
\end{proof}

\begin{theorem}
\label{thm:balls_bins:upper_bound_expectation_nonnegative_function}
If $f(x_1, \dots, x_n)$ is a nonnegative function, then
\[
\E\left[f\big(X_1^{(m)}, \dots, X_n^{(m)}\big)\right]
\leq
e\sqrt{m} \cdot \E\left[f\big(Y_1^{(m)}, \dots, Y_n^{(m)}\big)\right].
\]
\end{theorem}

\begin{proof}
Use Theorem~\ref{thm:balls_bins:throw_m_balls_into_n_bins} to obtain
%%
\begin{align*}
& \E\left[f\big(Y_1^{(m)}, \dots, Y_n^{(m)}\big)\right] \\[4pt]
&=
\sum_{k=0}^\infty
\E\left[
  f\big(Y_1^{(m)}, \dots, Y_n^{(m)}\big) \;\left|\; \sum_i Y_i^{(m)} = k\right.
\right]
\cdot \Pr\left(\sum_i Y_i^{(m)} = k\right) \\[4pt]
&\geq
\E\left[
  f\big(Y_1^{(m)}, \dots, Y_n^{(m)}\big) \;\left|\; \sum_i Y_i^{(m)} = m\right.
\right]
\cdot
\Pr\left(\sum_i Y_i^{(m)} = m\right) \\[4pt]
&=
\E\left[f\big(X_1^{(m)}, \dots, X_n^{(m)}\big)\right]
\cdot \Pr\left(\sum_i Y_i^{(m)} = m\right).
\end{align*}
%%
By Lemma~\ref{lem:balls-bins:sum_Poisson_random_variables}, the sum
$\sum_i Y_i^{(m)}$ is a Poisson random variable with mean $m$. Thus
\[
\E\left[f\big(Y_1^{(m)}, \dots, Y_n^{(m)}\big)\right]
\geq
\E\left[f\big(X_1^{(m)}, \dots, X_n^{(m)}\big)\right]
\cdot \frac{m^m e^{-m}}{m!}
\]
and using the bound
\[
m!
<
e\sqrt{m} \left(\frac{m}{e}\right)^m
\]
we conclude that
\[
\E\left[f\big(Y_1^{(m)}, \dots, Y_n^{(m)}\big)\right]
\geq
\E\left[f\big(X_1^{(m)}, \dots, X_n^{(m)}\big)\right]
\cdot \frac{1}{e\sqrt{m}}
\]
and the theorem follows.
\end{proof}

\begin{lemma}
\label{lem:balls_bins:upper_bound_n_factorial}
For any integer $n \geq 0$, we have
\[
n!
\geq
e\sqrt{n} \left(\frac{n}{e}\right)^n.
\]
\end{lemma}

\begin{proof}
Write $\ln(n!) = \sum_{i=1}^n \ln i$. For $i \geq 2$,
\[
\int_{i-1}^i \ln x \; dx
\geq
\frac{\ln(i-1) + \ln i} {2}
\]
since $\ln x$ is concave. Then
\[
\int_1^n \ln x \; dx
\geq
\sum_{i=1}^n \ln i - \frac{\ln n}{2}
\]
which is equivalent to
\[
n \cdot \ln n - n + 1
\geq
\ln(n!) - \frac{\ln n}{2}
\]
whence the lemma follows by exponentiating both sides.
\end{proof}

Describe by ``Poisson case'' the situation where the number of balls
in the bins are independent Poisson random variables with mean
$m/n$. And by ``exact case'' we refer to the scenario in which $m$
balls are thrown independently and uniformly at random into $n$
bins. Then the following is an immediate consequence of
Theorem~\ref{thm:balls_bins:upper_bound_expectation_nonnegative_function}.

\begin{corollary}
An event that takes place with probability $p$ in the Poisson case
takes place with probability $\leq pe\sqrt{m}$ in the exact case.
\end{corollary}

\begin{proof}
Let $f$ be the indicator function that is $1$ if an event occurs and
$0$ otherwise. Then $\E[f]$ is the probability that the event occurs
and the result immediately follows from
Theorem~\ref{thm:balls_bins:upper_bound_expectation_nonnegative_function}.
\end{proof}

\begin{theorem}
Consider a nonnegative function $f(x_1, \dots, x_n)$ such that the
expectation $\E\left[f\big(X_1^{(m)}, \dots, X_n^{(m)}\big)\right]$ is
either monotonically increasing or monotonically decreasing in
$m$. Then we have
\[
\E\left[f\big(X_1^{(m)}, \dots, X_n^{(m)}\big)\right]
\leq
2 \cdot \E\left[f\big(Y_1^{(m)}, \dots, Y_n^{(m)}\big)\right].
\]
\end{theorem}

\begin{proof}
The following is an outline of a proof. The proof of
Theorem~\ref{thm:balls_bins:upper_bound_expectation_nonnegative_function}
shows that for any nonnegative function $f$ we have
\[
\E\left[f\big(Y_1^{(m)}, \dots, Y_n^{(m)}\big)\right]
\geq
\E\left[f\big(X_1^{(m)}, \dots, X_n^{(m)}\big)\right]
\cdot \Pr\left(\sum_i Y_i^{(m)} = m\right).
\]
If $\E\left[f\big(X_1^{(m)}, \dots, X_n^{(m)}\big)\right]$ is
monotonically increasing in $m$, we need to show that
\[
\E\left[f\big(Y_1^{(m)}, \dots, Y_n^{(m)}\big)\right]
\geq
\E\left[f\big(X_1^{(m)}, \dots, X_n^{(m)}\big)\right]
\cdot \Pr\left(\sum_i Y_i^{(m)} \geq m\right).
\]
Make a similar statement for the case where
$\E\left[f\big(X_1^{(m)}, \dots, X_n^{(m)}\big)\right]$ is
monotonically decreasing in $m$.

Consider a Poisson random variable $Z$ with mean $\mu$, where
$\mu \geq 1$ is an integer. We need to show that
$\Pr(Z \geq \mu) \geq 1/2$ and $\Pr(Z \leq \mu) \geq 1/2$.

Conclude by the above results that the theorem holds.
\end{proof}

\begin{corollary}
Consider an event $\varepsilon$ whose probability is either
monotonically increasing or monotonically decreasing in the number of
balls. If $\varepsilon$ has probability $p$ in the Poisson case, then
$\varepsilon$ has probability $2p$ in the exact case.
\end{corollary}

\begin{lemma}
Let $n$ balls be thrown independently and uniformly at random into $n$
bins. Then the maximum load is at least
\[
\frac{\ln n}{\ln \ln n}
\]
with probability $\geq 1 - 1/n$ for sufficiently large $n$.
\end{lemma}

\begin{proof}
Set
\[
M
=
\frac{\ln n}{\ln \ln n}.
\]
In the Poisson case there is a probability $\geq \frac{1}{e} M!$ that
the load of bin $1$ is $\geq M$. As all bins are independent in the
Poisson case, the probability that no bin has load $\geq M$ is less
than or equal to
\[
\left(1 - \frac{1}{eM!}\right)^n
\leq
\exp\left\{\frac{-n} {eM!}\right\}.
\]
It suffices to show that
\[
M!
\leq
\frac{n} {2e \cdot \ln n}
\]
or equivalently show that
\[
\ln(M!)
\leq
\ln n - \ln \ln n - \ln(2e).
\]
Use Lemma~\ref{lem:balls_bins:upper_bound_n_factorial} to get
\[
M!
\leq
e\sqrt{M} \left(\frac{M}{e}\right)^M
\leq
M \left(\frac{M}{e}\right)^M
\]
when $n$ and $M$ are sufficiently large. Use the result
$\ln \ln n = O(\ln n / \ln \ln n)$ to obtain
%%
\begin{align*}
\ln(M!)
&\leq
M \cdot \ln M - M + \ln M \\[4pt]
&=
\frac{\ln n}{\ln \ln n} \cdot (\ln \ln n - \ln \ln \ln n)
- \frac{\ln n}{\ln \ln n} + (\ln \ln n - \ln \ln \ln n) \\[4pt]
&\leq
\ln n - \frac{\ln n}{\ln \ln n} \\[4pt]
&\leq
\ln n - \ln \ln n - \ln(2e)
\end{align*}
%%
as required.
\end{proof}
